package algoritmo;

import java.awt.Point;
import java.util.LinkedList;

/**
 * A* pathfinding.
 * Encontra um caminho at� um destino a partir de uma origem. O caminho ser� m�nimo e v�lido.
 * Se o destino for inv�lido, essa classe pode causar uma excess�o n�o controlada.
 */
public class PathFinding
{
	private class PfPoint implements Comparable
	{
		public Point p;
		public PfPoint parent;
		
		/*
		 * Custo da origem at� aqui
		 */
		public int value;
		public int estimative;

		public PfPoint(Point p, int value, PfPoint parent, Point destiny)
		{
			this.p = p;
			this.value = value;
			this.parent = parent;
			this.estimative = estimate(destiny);
		}
		
		/*
		 * Estima custo at� o destino.
		 */
		private int estimate(Point destiny)
		{
			return Constantes.manhattan(destiny, p);
		}
		
		@Override
		public boolean equals(Object that)
		{
			 if (this == that) 
				 return true;
			 
			 if ( !(that instanceof PfPoint) )
				 return false;
			 
			 // sao iguais se pontos forem iguais
			 return p.equals(((PfPoint)that).p);
		}

		@Override
		public int compareTo(Object that) 
		{
			if ( !(that instanceof PfPoint) )
				return -1;
			
			PfPoint o = (PfPoint)that;
			int myVal = value + estimative;
			int hisVal = o.value + o.estimative;
			
			if (myVal > hisVal)
				return 1;
			else if (myVal < hisVal)
				return -1;
			
			return 0;
		}
		
		@Override
		public int hashCode()
		{
			return Constantes.MUNDO_TAM * p.x + p.y;
		}		
	}
	
	private int[][] mundo;
	private BinaryHeap openList;
	private boolean[] closedList;
	
	private Point origin;
	private Point destiny;
	
	private PfPoint pfDestiny;
	private Point nextPointToGo;
	private boolean caminhoBuscado;
	private int numeroMoedas;
	
	private Poupador agente;
	
	public PathFinding(Poupador agente, int[][] mundo, Point origin, Point destiny)
	{
		this.mundo = mundo;
		this.origin = origin;
		this.destiny = destiny;
		this.pfDestiny = null;
		this.caminhoBuscado = false;
		this.numeroMoedas = agente.sensor.getNumeroDeMoedas();
		
		this.agente = agente;
		
		openList = new BinaryHeap(Constantes.MUNDO_TAM * 4, true);
		closedList = new boolean[Constantes.MUNDO_TAM * Constantes.MUNDO_TAM];
		
		
		for(int i = 0; i < closedList.length; i++)
			closedList[i] = false;
	}		
	
	private PfPoint isOpen(PfPoint p)
	{		
		return (PfPoint)openList.get(p);
	}
	
	private void addOpenPoint(PfPoint p)
	{
		openList.add(p);
	}
	
	/**
	 * Informa se um ponto eh valido e se existe algum custo adicional para se mover para aquele ponto dependendo da situação.
	 * @param pos
	 * @param custoAdicionalMovimento
	 * @return
	 */
	private boolean isValidPoint(Point pos, Holder<Integer> custoAdicionalMovimento)
	{
		boolean valido = Constantes.isValidPoint(pos, numeroMoedas, mundo);	
		custoAdicionalMovimento.value = 0; // por padrao, não há custo adicional para se mover
		
		if (valido)
		{
			int valorCelula = mundo[pos.y][pos.x];
			Holder<Integer> distanciaLadrao = new Holder<Integer>(0);
			Point posLadrao = agente.ladraoMaisProximo(pos, distanciaLadrao);
			
			switch(valorCelula)
			{
				// pastilhas sao caras, evitamos pegá-las a nao ser q hajam ladroes proximos
				case Constantes.VISAO_PASTILHA:
					valido = posLadrao != null && distanciaLadrao.value < 4;
					break;			
			}		
			
			// aqui consideramos desviar e evitar caminhos com ladroes
			// vamos considerar apenas caminhos validos e se tivermos moeda (pois c.c. nao vale a pena desviar)
			if (numeroMoedas > 0)
			{
				// devemos evitar ir para quadros que nos deixem perigosamente proximos dos ladroes
				// nao devemos evitar quadros muito distantes da nossa posição inicial pois isso poderia
				// impedir que alguns caminhos fossem completados (ainda nao sei o quão bom é isso)
				// TODO:
				// considerar caminhos não completados - ex. se vamos ao banco e há ladrões próximos do banco
				// e evitamos caminhos proximos a ladroes, entao possivelmente nao encontraremos um caminho até o
				// banco, mas isso pode ser bom pois tentaremos fazer outra coisa, contudo podemos estar suficientemente
				// longo do banco para que ao chegarmos mais próximo dele, os ladrões tenham ido fazer outra coisa
				
				int distMovimento = Constantes.manhattan(pos, origin);
				
				// apenas vamos considerar pontos inseguros na região do nosso campo de visão
				// além disso é pura especulação
				if (distMovimento < 6)
				{				
					int distDiff;
					
					// apenas vamos verificar se eh seguro, se existir ladrao proximo e se estiver suficientemente proximo
					// para nos ameacar
					if (posLadrao != null && ((distDiff = distMovimento - distanciaLadrao.value)) > -Constantes.MIN_DIST_LADRAO)
					{
						// aumentamos o custo proporcionalmente a quão provavel eh um roubo naquele quadro
						custoAdicionalMovimento.value += 100 * (Constantes.MIN_DIST_LADRAO + distDiff);
					}
				}
			}
		}
		
		return valido;
	}
	
	/**
	 * Adiciona ponto a openList.
	 * Se jah existir l�, ent�o faz atualiza��es do caminho de acordo.
	 */
	private void openPoint(PfPoint p)
	{
		Holder<Integer> custoAdicional = new Holder<Integer>(0);
		// se ponto nao eh valido ou estah na lista de fechados, nao fa�a nada
		if (!isValidPoint(p.p, custoAdicional) || isClosed(p))
			return;

		// adicionamos o custo adicional de movimento
		p.value += custoAdicional.value;
		PfPoint pInList = isOpen(p);
		
		// se ponto nao existe, apenas o adicionamos na lista
		if (pInList == null)
			addOpenPoint(p);
		else
		{		
			// se encontramos uma forma melhor de atingir o ponto p
			// entao atualizamos essa forma
			if (pInList.value > p.value)
			{
				pInList.value = p.value;
				pInList.parent = p.parent;
			}
		}
	}
	
	private boolean isClosed(PfPoint p)
	{
		return closedList[p.hashCode()];
	}
	
	/**
	 * Fecha ponto e indica se ponto fechado eh o destino
	 */
	private void closePoint(PfPoint p)
	{		
		if (!isClosed(p))
			closedList[p.hashCode()] = true;
	}
	
	/*
	 * Olha pontos em vonta de p e os coloca na openList, incluindo p
	 */
	private void lookAround(PfPoint p)
	{
		// o custo de ir de p a algum outro ponto � 1
		int value = p.value + 1;

		// cima
		Point np = new Point(p.p.x, p.p.y - 1);
		openPoint(new PfPoint(np, value, p, destiny));
		
		// baixo
		np = new Point(p.p.x, p.p.y + 1);
		openPoint(new PfPoint(np, value, p, destiny));
		
		// esquerda
		np = new Point(p.p.x - 1, p.p.y);
		openPoint(new PfPoint(np, value, p, destiny));
		
		// direita
		np = new Point(p.p.x + 1, p.p.y);
		openPoint(new PfPoint(np, value, p, destiny));
	}
	
	/*
	 * Retorna ponto de menor custo na lista de abertos e o retira da lista.
	 */
	private PfPoint popLowestCostPoint()
	{	
		PfPoint min = null;	
		
		min = (PfPoint)openList.pop();
		
		return min;
	}
	
	/*
	 * Acha o caminho
	 */
	private void findPath()
	{
		// informa q jah foi feita busca pelo caminho
		caminhoBuscado = true;
		
		if (origin.equals(destiny))
			return;
		
		// custo da origem eh 0 e nao tem pai
		PfPoint pfOrigin = new PfPoint(origin, 0, null, destiny);
		
		// adiciona pontos proximos a origem na lista de abertos		
		lookAround(pfOrigin);
		// entao fecha origem
		closePoint(pfOrigin);		
		
		PfPoint p;
		
		// enquanto tivermos pontos a olhar
		// pega ponto de menor custo e o remove da lista (getLowestCostPoint faz isso)
		while ( ( p = popLowestCostPoint() ) != null )
		{
			// se p for igual ao destino, podemos parar
			if (p.p.equals(destiny))
			{
				this.pfDestiny = p;
				break;
			}
			
			// fecha ponto de menor custo
			closePoint(p);
			// olha em vonta do ponto de menor custo
			lookAround(p);
		}
		
		// se ha caminho, entao ponto de destino foi preenchido
		if (pfDestiny != null)
		{
			p = pfDestiny;
			
			// se jah estamos onde queremos ir, nao temos o q fazer
			if (origin.equals(pfDestiny.p))
			{
				nextPointToGo = null;
			}
			else
			{
				// procura ponto antes da origem
				while (p.parent.parent != null)
					p = p.parent;
				
				// proximo ponto a ir eh aquele q vem depois da origem (origem tem pai nulo)
				nextPointToGo = p.p;
				// descartamos origem
				p.parent = null;
			}
		}
	}
	
	/*
	 * Retorna proximo ponto do caminho
	 */
	public Point findNextPoint()
	{
		if (!caminhoBuscado)
			findPath();
				
		// jah sabemos para onde ir
		Point ret = nextPointToGo;
		
		// vamos deixar proximo preparado
		// TODO: nao implementado
			
		return ret;
	}
	
	/**
	 * Realiza busca de caminho ótimo até o ponto de destino, retornando a acao a ser tomada.
	 * @param agente
	 * @param mundo
	 * @param posicaoAtual
	 * @param destino
	 * @return
	 */
	public static int tomarMelhorDecisao(Poupador agente, int[][] mundo, Point posicaoAtual, Point destino)
	{
		int acao;
		PathFinding pf = new PathFinding(agente, mundo, posicaoAtual, destino);
		Point proximoQuadro = pf.findNextPoint();

		if (proximoQuadro != null)
		{
			acao = Constantes.tomarAcao(posicaoAtual, proximoQuadro);
		}
		else
			acao = Constantes.PARADO;
		
		return acao;
	}
}
